package day_2022_12_to_3.year2023;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author haomin
 * @date 2023/01/17 22:41
 **/
public class Day1_17_Review {
    class Solution29 {
        public int[] spiralOrder(int[][] matrix) {
            if(matrix.length == 0 || matrix[0].length == 0) return new int[0];
            int m = matrix.length, n = matrix[0].length;
            int l = 0, r = n-1, u = 0, d = m-1;
            List<Integer> list = new LinkedList<>();
            while(true) {
                for(int i = l; i <= r; ++i) list.add(matrix[u][i]);
                if(++u > d) break;

                for(int i = u; i <= d; ++i) list.add(matrix[i][r]);
                if(--r < l) break;

                for(int i = r; i >= l; --i) list.add(matrix[d][i]);
                if(--d < u)  break;

                for(int i = d; i >= u; --i) list.add(matrix[i][l]);
                if(++l > r) break;
            }
            return list.stream().mapToInt(Integer::intValue).toArray();
        }
    }

    class MinStack {
        Deque<Integer> s1;
        Deque<Integer> s2; // minstack

        /** initialize your data structure here. */
        public MinStack() {
            s1 = new LinkedList<>();
            s2 = new LinkedList<>();
        }

        public void push(int x) {
            s1.push(x);
            if(s2.isEmpty()) {
                s2.push(x);
            }else {
                s2.push(x < s2.peek() ? x : s2.peek());
            }
        }

        public void pop() {
            s1.pop();
            s2.pop();
        }

        public int top() {
            return s1.peek();
        }

        public int min() {
            return s2.peek();
        }
    }

    class Solution31 {
        public boolean validateStackSequences(int[] pushed, int[] popped) {
            Deque<Integer> s = new LinkedList<>();
            int j = 0;
            for(int i = 0; i < pushed.length; ++i) {
                s.push(pushed[i]);
                while(!s.isEmpty() && s.peek() == popped[j]) {
                    s.pop();
                    j++;
                }
            }
            return s.isEmpty();
        }
    }
}